Computer generated color and grey level images are composed of picture elements (pixels), each pixel represented by multiple bits which define either a color or a grey level. In order to represent such images on a bi-level (black and white) printer, the data, if not already grey level, is converted into a grey level multi-bit state and the individual grey level pixels are converted to binary level pixels, using a scaling and dithering process.
Pixels in a source multi-bit per pixel image are usually not at the resolution of the bi-level printer resolution and thus, must be scaled to match the printer's resolution. For instance, many modern printers exhibit a 600 dot-per-inch (dpi) resolution, whereas computers often provide images at a resolution of 1/6th or less than the printer's resolution. Accordingly, either the computer or the printer must spatially scale the lower resolution "source" image pixels to a required "destination" level resolution.
Many computers employ operating systems (such as the Microsoft "Windows" operating system) that require raster operations to be performed on scaled raster data. In such operating systems, it is imperative that any bit map scaling action be accurate and repeatable in a deterministic fashion. In other words, there must be a direct and repeatable correspondence of destination image pixels from each source image pixel, without regard for the scaling starting position in the bit map which represents the source image.
Prior art processes for scaling source bit map image data into destination image bit map data have required that each source pixel be scaled individually to preserve the accurate and deterministic scaling. Where, however, there is a repeat in the source image pixel data (i.e., a plurality of repeated identical pixel values), a "skip ahead" procedure has been utilized which enables the use of a repetition of the destination pixel data. Such a skip ahead procedure is described in U.S. patent application Ser. No. 08/238,277, filed May 3, 1994, entitled "Method to Convert Bit Maps to Monochrome Data," to Poppenga et al., and assigned the same Assignee as this application.
Before a skip ahead procedure can be implemented, an initial destination pixel corresponding to an initial source pixel where the skip ahead procedure is to end, must be identified. There is also a need to find such an initial destination pixel when the destination pixel corresponding to a source pixel commences at an interior pixel in a destination pixel bit map.
While a variety of scaling procedures exist in the prior art, a widely used procedure utilizes a pair of accumulated sums to enable the writing of a plurality of destination pixels which correspond to each succeeding source pixel (assuming a scale-up action). Hereafter, two examples will be given of the prior art scaling procedure, the first employing a 10-to-1 scale-up and the second employing a 3-to-5 scale-up. In the first example, it will be assumed that the source X extent is 60 pixels (the extent of the source bit map in the X direction) and the destination X extent is 600 pixels (the extent of the destination bit map in the X direction). The two variables employed during the procedure are Scale Source Sum and Scale Destination Sum. The scaling rules followed by the procedure are as follows:
1. If Scale Destination Sum is greater than or equal to Scale Source Sum, then read a source pixel and add the destination X extent to the Scale Source Sum. PA0 2. Whenever a destination pixel is written, add the source X extent to the Scale Destination Sum.
Example 1 below illustrates application of the scaling rules set out above.